package com.zhengb.algorithmdemo.leetcode.statck;

import java.util.Arrays;
import java.util.Stack;

/**
 * leetcode 779题
 * 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
 * <p>
 * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
 * <p>
 * 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/daily-temperatures
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zhengbo
 * @date 2020/2/19
 */
public class DailyTempratures {

    public static int[] dailyTemperatures(int[] T) {

        if (T.length == 0 || T.length == 1) {
            return new int[]{0};
        }
//        LinkListBaseStack<int[]> stack = new LinkListBaseStack<>();
        Stack<int[]> stack = new Stack<>();

        int[] result = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            //下表+对应值
            int[] curValue = new int[]{i, T[i]};
            //堆栈为空 先push当前元素
            if (stack.isEmpty() || stack.peek() == null) {
                stack.push(curValue);
                continue;
            }
            //当前值与堆栈top比较 如果大于top值 则将堆栈pop 不断循环操作 直到遇到元素>当前值
            while (!stack.isEmpty() && (stack.peek() != null) && (curValue[1] > stack.peek()[1])) {
                int[] pop = stack.pop();
                //两个元素下表的差值即为结果值 放入到result数组中
                result[pop[0]] = curValue[0] - pop[0];
            }
            //如果当前值<堆栈top值 则压入栈
            stack.push(curValue);
        }

        return result;
    }

    public static void main(String[] args) {


        System.out.println(Arrays.toString(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
    }
}
